
#pragma once
#include<iostream>
#include<algorithm>
#include <iterator>
#include<string>
#include<fstream>
#include<vector>
#include<stdio.h>
#include<map>
const char add_string = '+';
const char erase_string = '-';

template <class iterator>
int LongestCommonPrefix(iterator a_begin, iterator a_end,
                        iterator b_begin, iterator b_end){
    int answer = 0;
    while(a_begin < a_end && b_begin < b_end && *a_begin == *b_begin){
        answer++;
        a_begin++;
        b_begin++;
    }
    return answer;
}

template<class iterator>
int ComputeEditDistance(
             iterator a_begin, iterator a_end,
             iterator b_begin, iterator b_end){
    int a_size = std::distance( a_begin, a_end );
    int b_size = std::distance( b_begin, b_end );
    if(b_size == a_size){
        bool flag = true;
        for(int i = 0; i < a_size; i++){
            if(*(a_begin + i) != *(b_begin + i)) flag = false;
        }
        if(flag) return 0;
    }
    int a_index;
    std::vector < int > XCoordinateOfFuthestPointOnGivenDiagonalWithGivenDistance;
    XCoordinateOfFuthestPointOnGivenDiagonalWithGivenDistance.resize(2*(a_size + b_size) + 1, -1);
    XCoordinateOfFuthestPointOnGivenDiagonalWithGivenDistance[a_size + b_size] = LongestCommonPrefix(a_begin, a_end, b_begin, b_end);
    for(int distance = 1; ; distance++){

        for(int diagonal = -distance; diagonal <= distance; diagonal += 2){
            if(diagonal == -distance || (diagonal != distance && XCoordinateOfFuthestPointOnGivenDiagonalWithGivenDistance[diagonal - 1 + a_size + b_size] < XCoordinateOfFuthestPointOnGivenDiagonalWithGivenDistance[diagonal + 1 + a_size + b_size])){
                a_index = XCoordinateOfFuthestPointOnGivenDiagonalWithGivenDistance[diagonal + 1 + a_size + b_size];
            }
            else{
                a_index = XCoordinateOfFuthestPointOnGivenDiagonalWithGivenDistance[diagonal - 1 + a_size + b_size] + 1;
            }
            int b_index = a_index - diagonal;
            if (b_index >= 0 && a_index >= 0 && a_index <= a_size && b_index <= b_size) {
            a_index += LongestCommonPrefix (a_begin + a_index, a_end, b_begin + b_index, b_end);
            }
            XCoordinateOfFuthestPointOnGivenDiagonalWithGivenDistance[diagonal + a_size + b_size] = a_index;
            b_index = a_index - diagonal;
            if(a_index == a_size && b_index == b_size){
                return distance;
            }
        }
    }
}

struct point{
    int x;
    int y;

    point(int x_,int y_) : x(x_), y(y_) {}

    bool operator == (const point &tmp)const {return (x == tmp.x && y == tmp.y);}
    bool operator <(const point &tmp)const {return (x < tmp.x);}
};


template<class iterator>
std::vector<int> GetXCoordinatesOfPointsWhichHaveGivenDistance(
        int distance, int offset,
        iterator a_begin, iterator a_end,
        iterator b_begin, iterator b_end){
    int a_size = std::distance(a_begin, a_end);
    int b_size = std::distance(b_begin, b_end);
    std::vector< int > answer (2 * (a_size + b_size) + 1, -1);
    answer[a_size + b_size] = LongestCommonPrefix(a_begin, a_end, b_begin, b_end);
    for(int current_distance = 1; current_distance <= distance; current_distance++){
        int left_edge = std::min(current_distance, b_size);
        int right_edge = std::min(current_distance, a_size);
        if((current_distance - left_edge)  %2 == 1) left_edge--;
        if((current_distance - right_edge)%2 == 1) right_edge--;
        int a_index;
        for(int diagonal = -left_edge; diagonal <= right_edge; diagonal += 2){
            a_index = std::min( std::min( std::max(answer[diagonal + 1 + offset], answer[diagonal - 1 + offset] + 1), a_size), diagonal + b_size);
            int b_index = a_index - diagonal;
            if(b_index < b_size && a_index < a_size && b_index >= 0 && a_index >= 0){
                a_index += LongestCommonPrefix(a_begin + a_index, a_end, b_begin + b_index, b_end);
            }
            answer[diagonal + offset] = a_index;
        }
    }
    return answer;
}


template<class iterator>
point FindOverlapPoint(int distance, iterator a_begin, iterator a_end,
                                     iterator b_begin, iterator b_end){


    int a_size = std::distance( a_begin, a_end );
    int b_size = std::distance( b_begin, b_end );
    int delta = a_size - b_size;
    std::reverse_iterator <iterator> a_end_reverse(a_begin);
    std::reverse_iterator <iterator> a_begin_reverse (a_end);
    std::reverse_iterator <iterator> b_end_reverse (b_begin);
    std::reverse_iterator <iterator> b_begin_reverse (b_end);

    std::vector<int> XCoordinatesOfPointsWhichHaveGivenDistanceFromBeginning = GetXCoordinatesOfPointsWhichHaveGivenDistance((distance+1)/2, b_size + a_size, a_begin, a_end, b_begin, b_end);
    std::vector<int>   XCoordinatesOfPointsWhichHaveGivenDistanceFromEnd = GetXCoordinatesOfPointsWhichHaveGivenDistance((distance)/2, b_size + a_size, a_begin_reverse, a_end_reverse, b_begin_reverse, b_end_reverse);
    for(int diag = std::min(a_size, (distance + 1)/2) ; diag >= std::max(-(distance + 1)/2, -b_size); diag--){
        if(XCoordinatesOfPointsWhichHaveGivenDistanceFromBeginning[diag + b_size + a_size] + XCoordinatesOfPointsWhichHaveGivenDistanceFromEnd[delta - diag + b_size + a_size]>= a_size){
            int x = XCoordinatesOfPointsWhichHaveGivenDistanceFromBeginning[diag + b_size + a_size];
            point overlap_point (x, x - diag);
            return overlap_point;
        }
    }
}

template <class iterator>
void GetPointsWhichLayOnShortestPath(int distance, std::vector<point> &points_which_lay_on_shortest_path,
        iterator a_begin, iterator a_end, int a_offset,
        iterator b_begin, iterator b_end, int b_offset ){
    int a_size = std::distance(a_begin, a_end);
    int b_size = std::distance(b_begin, b_end);
    if(a_size == 0 || b_size == 0) return;
    if(distance == 0){
        for(int i = 0; i < a_size; i++){
            point temp (a_offset + i, b_offset + i);
            points_which_lay_on_shortest_path.push_back(temp);
        }
        return;
    }

    if(distance == 1){
        int a_index = 0;
        while (a_index < a_size && a_index < b_size && (a_begin[a_index] == b_begin[a_index])){
            point temp (a_offset + a_index, b_offset + a_index);
            points_which_lay_on_shortest_path.push_back(temp);
            a_index++;
        }
        int b_index = a_index;
        if(a_size > b_size) a_index++;
        else b_index++;
        while(a_index < a_size){
            point temp (a_offset + a_index, b_offset + b_index);
            points_which_lay_on_shortest_path.push_back(temp);
            a_index++;
            b_index++;
        }
        return;
    }

    point divide_point = FindOverlapPoint(distance, a_begin, a_end, b_begin, b_end);
    int dx = divide_point.x;
    int dy = divide_point.y;
    GetPointsWhichLayOnShortestPath((distance+1)/2, points_which_lay_on_shortest_path, a_begin, a_begin + dx, a_offset, b_begin, b_begin + dy, b_offset);
    GetPointsWhichLayOnShortestPath((distance)/2, points_which_lay_on_shortest_path, a_begin + dx, a_end, a_offset + dx,  b_begin + dy, b_end, b_offset + dy);
}

inline std::vector<std::string> FormatEditScript(std::vector<point> &points_which_lay_on_shortest_path,
        const std::vector<std::string>& file_a, const std::vector<std::string>& file_b){
    int current_point = 0;
    int a_size = file_a.size();
    int b_size = file_b.size();
    point t (a_size,b_size);
    points_which_lay_on_shortest_path.push_back(t);
    std::vector<std::string > answer;
    int a_index = points_which_lay_on_shortest_path[current_point].x;
    int b_index = points_which_lay_on_shortest_path[current_point].y;
    int a_position = 0;
    int b_position = 0;
    while(current_point < points_which_lay_on_shortest_path.size()){
        while(a_position < a_index){
            answer.push_back(erase_string + *(file_a.begin() + a_position));
            a_position++;
        }
        while(b_position < b_index) {
            answer.push_back (add_string + *(file_b.begin() + b_position));
            b_position++;
        }
        if(a_position < a_size) answer.push_back(*(file_a.begin() + a_position));
        a_position++;
        b_position++;
        current_point++;
        a_index = points_which_lay_on_shortest_path[current_point].x;
        b_index = points_which_lay_on_shortest_path[current_point].y;
    }
    while(a_position < a_size){
        answer.push_back (erase_string + *(file_a.begin() + a_position));
        a_position++;
    }
    while(b_position < b_size){
        answer.push_back(add_string + *(file_b.begin() + b_position));
        b_position++;
    }
    return answer;
}




inline std::vector<int> digitize(const std::vector<std::string>& strings, std::map<std::string, int> &string_cache){
    std::vector<int> result;
    for (int i=0; i<strings.size(); i++) {
        result.push_back(string_cache.insert(std::pair<std::string, int>(strings[i], 
			string_cache.size())).first->second);
    }
    return result;
}





inline std::vector<std::string> GetEditScript( std::vector<std::string>& file_a,  std::vector<std::string>& file_b){
    std::map<std::string,int>  map;
    std::vector<int> digitized_a = digitize(file_a, map);
    std::vector<int> digitized_b = digitize(file_b, map);
    int distance = ComputeEditDistance(digitized_a.begin(), digitized_a.end(), digitized_b.begin(), digitized_b.end());
    std::vector<point> points_which_lay_on_shortest_path;
    GetPointsWhichLayOnShortestPath(distance, points_which_lay_on_shortest_path, digitized_a.begin(), digitized_a.end(), 0, digitized_b.begin(), digitized_b.end(), 0);
    std::vector < std::string> answer = FormatEditScript(points_which_lay_on_shortest_path, file_a, file_b);
    return answer;
}


